package struct;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class FreqStack {

    public static void main(String[] args) {
        FreqStack freqStack = new FreqStack();
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(5);
        freqStack.push(7);
        freqStack.push(4);
        freqStack.push(5);

        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
        System.out.println(freqStack.pop());
    }


    private int topTimes;

    private final HashMap<Integer, LinkedList<Integer>> maxFreqStack;

    private final Map<Integer, Integer> countTable;

    public FreqStack() {
        maxFreqStack = new HashMap<>();
        countTable = new HashMap<>();
    }

    public void push(int num) {
        countTable.put(num, countTable.getOrDefault(num, 0) + 1);
        // 获取当前元素出现次数
        int count = countTable.get(num);
        // 更新最大频率
        topTimes = Math.max(topTimes, count);

        LinkedList<Integer> freqList = maxFreqStack.getOrDefault(count, new LinkedList<>());
        freqList.addLast(num);
        maxFreqStack.put(count, freqList);
    }

    public int pop() {
        if (topTimes == 0) {
            return -1;
        }

        LinkedList<Integer> maxFreqList = maxFreqStack.get(topTimes);
        Integer removedLast = maxFreqList.removeLast();

        // 为空更新最大频率
        if (maxFreqList.isEmpty()) {
            maxFreqStack.remove(topTimes);
            topTimes--;
        }

        // 更新频率表
        countTable.put(removedLast, countTable.get(removedLast) - 1);
        if (countTable.get(removedLast) <= 0) {
            countTable.remove(removedLast);
        }

        return removedLast;
    }

}
